#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef int ElemType;

// 定义带头结点的链表
typedef struct LNode
{
    ElemType data;
    LNode *next;
} LNode, *LinkList;

// 判断链表是否为空
bool Empty(LinkList L)
{
    return L->next == NULL;
}

// 头插法初始化链表
void InitListHead(LinkList &L, int len)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *node;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = rand() % 100;
        node->next = L->next;
        L->next = node;
    }
}

// 尾插法初始化链表
void InitListTail(LinkList &L, int len)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *tail = L, *node;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = rand() % 100;
        node->next = tail->next;
        tail->next = node;
        tail = node;
    }
}

// 返回链表长度
int Length(LinkList L)
{
    int len = 0;
    LinkList p = L->next;
    while (p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

// 通过元素值获取链表结点
LNode *LocateElem(LinkList L, ElemType e)
{
    LNode *p = L->next;
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}

// 获取链表第i个结点
LNode *GetElem(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    int j = 0;
    LNode *p = L;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}

// 将元素e插入到链表第i个位置
void ListInsert(LinkList &L, int i, ElemType e)
{
    LNode *p = GetElem(L, i - 1);
    if (p == NULL)
    {
        return;
    }
    LNode *node = (LNode *)malloc(sizeof(LNode));
    node->data = e;
    node->next = p->next;
    p->next = node;
}

// 删除链表第i个元素，元素值赋值给e
void ListDelete(LinkList &L, int i, ElemType &e)
{
    LNode *p = GetElem(L, i - 1);
    if (p == NULL || p->next == NULL)
    {
        return;
    }
    LNode *t = p->next;
    e = t->data;
    p->next = t->next;
    t->next = NULL;

    free(t);
}

// 打印链表
void PrintList(LinkList L)
{
    LNode *p = L->next;
    while (p != NULL)
    {
        printf("%3d", p->data);
        p = p->next;
    }
    printf("\n");
}

// 销毁链表
void DestoryList(LinkList &L)
{
    LNode *p = L;
    while (L != NULL)
    {
        L = L->next;
        free(p);
        p = L;
    }
}

int main()
{
    LinkList L;
    InitListTail(L, 9);
    PrintList(L);
    ListInsert(L, 5, 0);
    PrintList(L);
    LNode *node = LocateElem(L, 0);
    PrintList(node);
    ElemType e;
    ListDelete(L, 5, e);
    printf("delete index:%d elem:%d", 5, e);
    printf("\n");
    int len = Length(L);
    printf("len:%d", len);
    printf("\n");
}